\ifdefined\isGesamtDokument
\else
\input{header.tex}
\fi

\newcommand\myIncludeGraphics[2][]{%
	\ifdefined\isGesamtDokument
  	\includegraphics[#1]{ex6_identifikation/#2}%
  	\else
  	\includegraphics[#1]{#2}%
	\fi
}

%>>>>>h1
\section{Identifikation}\label{identifikation}

Die \textit{Identifikation} ist neben der Verschlüsselung und digitalen Signaturen eine dritte grundlegende Technik aus der Kryptographie.

Bei der Identifikation geht es stets darum, dass ein \textit{Beweiser} versucht, einem \textit{Verifizierer} den Nachweis über eine bestimmte Eigenschaft zu erbringen. 

In \figurename~\ref{identifikation} ist dies beispielhaft dargestellt. Bob bekommt von einer unbekannten Handy-Nummer eine SMS. Bevor er vertrauliche Daten preisgibt möchte er sichergehen, dass die Nachricht wirklich von Alice kam.

\begin{figure}[hbtp]
\centering
\myIncludeGraphics[scale=0.3]{Grafiken/Identifikation.png}
\caption{Bob fordert einen Nachweis zur Identifikation.}
\label{identifikation}
\end{figure}

Hierbei unterscheidet man grundsätzlich zwischen drei unterschiedlichen Methoden:
\begin{itemize}
\item \textbf{Besitz} - Identifikation durch ein Besitztum des Beweisers, bspw. durch einen Schlüssel.
\item \textbf{Wissen} - Identifikation durch das Wissen über eine bestimmte Information, bspw. ein Passwort.
\item \textbf{Biometrisches Material} - Identifikation durch das Vorhandensein bestimmter biometrischer Merkmale, bspw. mit einem Fingerabdruck.
\end{itemize}

In der Kryptographie beschäftigen wir uns hauptsächlich mit der Identifikation durch Wissen. Die folgenden Ausführungen basieren auf dieser Methode.

%>>>h2
\subsection{Anwendungen \buchmann{15.1}}
Typischerweise findet die Identifikation Anwendung bei der Überprüfung von Zugangsberechtigungen, die an eine bestimmte Identität gebunden sind. Dies ist zum Beispiel bei der Anmeldung an einem PC oder beim Login auf einer Webseite der Fall, wie es in \figurename~\ref{anmeldemasken} dargestellt ist.

\begin{figure}[hbtp]
\centering
\myIncludeGraphics[scale=1]{Grafiken/Anmeldemasken.png}
\caption{Typische Anmeldemasken zur Identifikation durch Passwort.}
\label{anmeldemasken}
\end{figure}

Verfahren zur Identifikation nennt man \textit{Identifikationsprotokolle}. Mithilfe dieser Protokolle bringt der Beweiser dem Verifizierer den Nachweis, dass der Verifzierer gerade mit dem Beweiser kommuniziert oder kurz vorher mit ihm kommuniziert hat.

Um einen Betrug auszuschließen, muss die Identifikation in Realzeit erfolgen.

%>>>h2
\subsection{Passwörter \buchmann{15.2}}\label{passwoerter}
Passwörter dienen der Identifikation durch Wissen. Nur wer das Passwort kennt, wird vom Verifizierer authentifiziert.

\subsubsection{Funktionsweise}

\paragraph{Registrierung} Zunächst müssen sich Verifizierer und Beweiser auf ein Passwort einigen. Dies geschieht in der Regel durch eine Registrierung des Beweisers beim Verifizierer, der diesem sein gewünschtes Passwort $w$ mitteilt.

Der Verifizierer speichert den Funktionswert $f(w)$ in einem Passwortverzeichnis, wobei die Funktion $f$ eine Einwegfunktion ist. \figurename~\ref{registrierung} veranschaulicht diesen Prozess. 

\begin{figure}[hbtp]
\centering
\myIncludeGraphics[scale=0.5]{Grafiken/PW_Registrierung.png}
\caption{Registrierung eines Passworts beim Verifizierer}
\label{registrierung}
\end{figure}

In der Praxis wird für $f$ häufig der aus der Unix-Welt stammende Algorithmus $crypt$ verwendet, der ursprünglich auf DES basierte. \figurename~\ref{crypt} zeigt den Ablauf von crypt. Zunächst wird das Passwort $w$ auf acht Zeichen und jedes dieser Zeichen wiederum auf 7 Bits gekürzt, wodurch der 56-Bit DES-Key konstruiert wird. Mit diesem Key wird ein Block bestehend aus Nullen 25-mal mit DES verschlüsselt. Zum \glqq verschärfen\grqq{} des Algorithmus wird in jeder DES-Runde auf das Zwischenergebnis $E(R)$ eine Bitpermutation angewendet, abhängig von einer 12 Bit langen \textit{Salt}. Außerdem erschwert das Salt Tabellen-basierte Angriffe mit vorberechneten Werten. Ein weiterer nützlicher Effekt ist, dass es anhand der Passwort-Datei nicht erkennbar ist, wenn zwei Benutzer dasselbe Passwort haben (vorausgesetzt, das Salt ist unterschiedlich).

\begin{figure}[hbtp]
\centering
\myIncludeGraphics[scale=0.5]{Grafiken/crypt_unix.png}
\caption{Der crypt Algorithmus}
\label{crypt}
\end{figure}

Heute gebräuchlich sind verbesserte Varianten mit MD5 oder der Blockchiffre Blowfish, die mit längeren Salts arbeiten.

\paragraph{Identifikation} Wenn ein Benutzer Zugang zu einem System wünscht, schickt er sein Passwort $w$ an den Verifizierer. Wie in \figurename~\ref{login} dargestellt, liest dieser das zugehörige Salt $s$ aus dem Passwortverzeichnis, wendet die Einwegfunktion $f(w,s)$ an und vergleicht den Funktionswert mit dem für den Benutzer im Passwortverzeichnis hinterlegten Wert. Stimmen beide überein, gilt der Nachweis als erbracht und dem Benutzer wird der Zugang gewährt.

\begin{figure}[hbtp]
\centering
\myIncludeGraphics[scale=0.5]{Grafiken/PW_Login.png}
\caption{Identifikation beim Verifizierer}
\label{login}
\end{figure}

\subsubsection{Angriffe}
Im Passwortverzeichnis des Verifizierers wird nie das Passwort $w$ eines Beweisers, sondern stets nur der Funktionswert $f(w)$ abgelegt. Da $f$ eine Einwegfunktion ist bringt es einem Angreifer nichts, das Passwortverzeichnis auszuspähen. Er kann aus dem abgelegten Funktionswert das Passwort $w$ nicht in polynomieller Laufzeit ermitteln.

Das beschriebenen Passwort-Verfahren hat dennoch einige Sicherheitslücken und bietet somit Möglichkeiten für Angriffe.

\paragraph{Wörterbuch-Angriff}
Da sich der Beweiser sein Passwort merken muss und nach Möglichkeit nirgends hinterlegt (bspw. auf einem Zettel auf der Rückseite seiner Tastatur), wählt er häufig ein für ihn sehr einfaches Passwort wie bspw. den Namen eines Verwandten. Hierdurch wird ein Wörterbuch-Angriff ermöglicht. Der Angreifer bildet alle Wörter $w$ aus dem Wörterbuch und versucht sich damit zu identifizieren. Da das Wörterbuch nur wenige Elemente hat, kann dies bereits in sehr kurzer Zeit und mit wenig Rechenleistung durchgeführt werden. Wörterbuchangriffe können online und offline durchgeführt werden. Online bedeutet, dass der Betrüger nacheinander versucht alle Wörter zur Identifikation zu verwendenn. Bei einem Offline-Angriff wird die Passwort-Datei gestohlen. Dieser Angriff ist natürlich mächtiger, da bspw. die Anzahl der wiederholten Versuche durch den Verifizierer nicht begrenzt werden kann.

Verhindert werden kann dieser Angriff indem das Wörterbuch durch die Wahl zufälliger Buchstabenfolgen oder den Einsatz von Sonderzeichen und Ziffern eklatant vergrößert wird. Hierdurch wird es für den Beweiser jedoch auch schwieriger sich das Passwort zu merken. Dies kann umgangen werden indem das Passwort bspw. auf einer Chipkarte gespeichert wird. Das Identifikationsverfahren wird auf diese Weise von einer wissensbasierten Methode in eine Identifikation durch Besitztum überführt.

\paragraph{Abhören des Passworts}\label{abhoeren}
Ein Angreifer kann auch versuchen, das Passwort bei der Übertragung vom Beweiser an den Verifizierer mitzuhören. Erfährt er das Passwort, kann er sich anschließend selbst erfolgreich anmelden und als der Beweiser ausgeben.

Dieser Angriff ist insbesondere dann möglich, wenn zwischen Beweiser und Verifizierer eine große Entfernung liegt, bspw. bei der Anmeldung auf einer Internetseite. Der Angreifer könnte hier durch unterschiedliche Methoden wie dem Einsatz eines Keyloggers oder dem Sniffen des Netzwerks das Passwort abgreifen.

Neben dem Einsatz von abhörsicheren Übertragungsprotokollen wie \textit{https} und der Installation geeigneter Schutzsoftware beim Beweiser kann das Abhören effizient durch den Einsatz sogenannter \textit{Einmal-Passwörter} (vgl. \ref{einmal-pw}) verhindert werden.

\paragraph{Manipulation des Passwortverzeichnisses}
Ist das Passwortverfahren durch geeignete Maßnahmen vor allen oben genannten Angriffen geschützt, besteht für den Angreifer noch die Möglichkeit, das Passwortverzeichnis zu manipulieren und für einen anderen Benutzer, bspw. Peggy, den Funktionswert $f(w_1)$ seines eigenen Passworts $w_1$ zu hinterlegen. Hat er dies geschafft, kann er sich fortan stets als Peggy ausgeben.

Der Betrug wird erst aufgedeckt, sobald Peggy sich am System anzumelden versucht und die Identifikation mit ihrem eigenen Passwort $w_2$ fehlschlägt. Das Passwortverzeichnis muss daher durch geeignete Schutzmaßnahmen gegen unberechtigte Zugriffe geschützt werden.

%>>>h2
\subsection{Einmal-Passwörter \buchmann{15.3}}\label{einmal-pw}
Einen effizienten Schutz gegen das Abhören von Passwörtern bei der Übertragung vom Beweiser an den Verifizierer (vgl. \ref{abhoeren}) bietet der Einsatz von sogenannten \textit{Einmalpasswörtern}. Ein Einmalpasswort kann nur für einen Anmeldevorgang verwendet werden und wird danach vom Verifizierer nicht mehr als Nachweis für die Identifikation akzeptiert. Das Abhören eines Passworts durch einen Angreifer ist also nutzlos, da er das erlangte Passwort kein weiteres mal verwenden kann.

\subsubsection{Realisierung durch Passwort-Liste} 
Der Beweiser ist im Besitz einer geheimen Liste mit Passwörtern $w_1,w_2,\dotsc,w_n$. Der Verifizierer hat die Liste mit den entsprechenden Funktionswerten $f(w_1),f(w_3),\dotsc,f(w_n)$ unter einer Einwegfunktion $f$. Eine bekannte Umsetzung dieses Verfahrens sind die TAN-Listen im Online-Banking.

Wie beim herkömmlichen Passwortverfahren (vgl. \ref{passwoerter}) besteht die Gefahr, dass ein Angreifer in den Besitz der Passwortliste gerät, da der Beweiser die Passwörter lange vor einer Identifikation kennen und aufbewahren muss.

\subsubsection{Realisierung mit Funktion $f$}\label{einmal-pw-funktion}
Der oben aufgezeigte Angriff, bei dem die Passwort-Liste ausspioniert wird, kann durch den Einsatz einer Funktion $f$ und eines Startwerts $w_0$ verhindert werden. 

Beweiser und Verifizierer teilen sich die Kenntnis über $f$ und $w_0$. Die Passwörter sind: $$w_i = f^i(w_{i-1}), i\geq 1$$

Zur Umsetzung dieses Verfahrens gibt es zwei unterschiedliche Möglichkeit.

\paragraph{Geheime Funktion $f$}
Die Einmalpasswörter werden durch Anwendung der geheim gehaltenen Funktion $f$ auf das vorangegangene Passwort erzeugt.

\paragraph{Iterierte Anwendung der öffentlich bekannten Hashfunktion $f$ gemäß RFC 2289}
Der Beweiser erzeugt $r$ Passwörter nach dem Verfahren in \ref{einmal-pw-funktion}. Die Einmalpasswörter werden in der Reihenfolge $w_{r-1}, w_{r-2}, \ldots, w_0$ verwendet. Der Verifizierer wendet die Funktion $f$ auf das Passwort an und prüft nun, ob der berechnete Wert mit dem letzten Passwort übereinstimmt.

%>>>h2
\subsection{Challenge-Response-Identifikation \buchmann{15.4}}
Ein Problem der bislang beschriebenen Identifikationsprotokolle besteht darin, dass der Beweiser stets das eigene Passwort und somit sein geheimes Wissen, das er zur Identifikation benötigt, an den Verifizierer überträgt. Ein Angreifer kann also jederzeit das Passwort mithören und selbst für die Identifikation beim Verifizierer nutzen. Das funktioniert sogar bei Einmal-Passwörtern.

Die Lösung für dieses Problem sind so genannte Challenge-Response-Verfahren zur Identifikation. Generell basiert dieses Verfahren auf der Idee, dass der Verifizierer dem Beweiser eine Aufgabe (\textit{challenge}) stellt, die dieser nur mit seinem geheimen Wissen (\textit{secret}) lösen kann und daraufhin dem Verifizierer die Lösung (\textit{response}) zusendet. Wie in \figurename~\ref{challenge-response} veranschaulicht, wird bei der Übertragung also nie das Geheimnis des Beweisers selbst, sondern stets nur eine Lösung des Rätsels übertragen. 

\begin{figure}[hbtp]
\centering
\myIncludeGraphics[scale=0.5]{Grafiken/challenge-response.png}
\caption{Challenge-Response-Verfahren}
\label{challenge-response}
\end{figure}

In der Praxis wird als challenge häufig eine Zufallszahl vom Verifizierer erzeugt, die vom Beweiser durch ein kryptographisches Verfahren verschlüsselt oder gehasht wird. Das secret ist damit der Schlüssel des Verschlüsselungsverfahrens. Als response und somit als Lösung wird der cipher-Text übertragen.

\paragraph{Replay-Angriff} Da für jede Identifikation eine neue challenge gestellt wird, nützt es einem Angreifer nichts, während einer Identifikation die challenge oder die response abzufangen und für eine eigene Identifikation zu einem späteren Zeitpunkt zu verwenden. Hierbei ist jedoch wichtig, dass für jede Identifikation eine neue challenge gestellt wird und die Anzahl der möglichen challenges hinreichend groß ist, um einen \textit{Replay-Angriff} durch das Ansammeln der responses zu verhindern.

\paragraph{Known-Plaintext-Angriff} Um einen Angriff durch Abhören zu verhindern, muss das Lösungsverfahren so gewählt sein, dass man aus einer abgefangenen challenge und einer dazugehörigen response nicht auf das geheime Wissen des Beweisers schließen kann und somit kein \textit{Known-Plaintext-Angriff} möglich ist. Im Folgenden werden einiger solcher Verfahren vorgestellt.

%>h3
\subsubsection{Verwendung von symmetrischer Kryptographie \buchmann{15.4.1}}\label{symmetrische_krypt}
Ein sehr einfaches Challenge-Response-Verfahren ist der Einsatz einer symmetrischen Verschlüsselung. Der Key ist hier das geheime Wissen. Sowohl Beweiser als auch Verifizierer müssen den gemeinsamen Schlüssel $k$ kennen.

In \figurename~\ref{cr_symmetrisch} wird das Verfahren visualisiert. Der Verifizierer Victor sendet an den Beweiser Peggy eine Zufallszahl $r$. Peggy verschlüsselt die Zufallszahl und bildet somit $c=E_k(r)$. Sie schickt $c$ an Victor, der dieses mit $r'=D_k(c)$ entschlüsselt. Victor vergleicht nun, ob $r'=r$ gilt. Falls ja, ist Peggy identifiziert.

\begin{figure}[hbtp]
\centering
\myIncludeGraphics[scale=0.5]{Grafiken/cr_symmetrisch.png}
\caption{Challenge-Response-Verfahren mit symmetrischer Kryptographie}
\label{cr_symmetrisch}
\end{figure}

Der entscheidende Nachteil, vor allem bei einer Client-Server Authentifizierung ist, dass der Server als Beweiser den geheimen Schlüssel kennen muss. Dieser liegt somit im Netz und muss vor unberechtigtem Zugriff geschützt werden. Ein Angreifer könnte ansonsten den geheimen Schlüssel $k$ ausspähen und sich damit das geheime Wissen zu eigen machen, welches zur Identifikation benötigt wird.

%>h3
\subsubsection{Verwendung von Public-Key-Kryptographie \buchmann{15.4.2}}
Eine bessere Variante als in \ref{symmetrische_krypt} ist die Verwendung eines Signaturverfahrens, was durch \figurename~\ref{cr_asymmetrisch} veranschaulicht ist. In diesem Fall besteht nicht die Möglichkeit den geheimen Schlüssel im Netzwerk auszulesen.

\begin{figure}[hbtp]
\centering
\myIncludeGraphics[scale=0.5]{Grafiken/cr_asymmetrisch.png}
\caption{Challenge-Response-Verfahren mit asymmetrischer Kryptographie}
\label{cr_asymmetrisch}
\end{figure}

Bei diesem Verfahren muss verhindert werden, dass ein Angreifer heimlich den Public-Key von Peggy auf Seite des Verifizierers Victor austauscht. Gelingt dies dem Angreifer, kann er sich als Peggy identifizieren.

%>h3
\subsubsection{Zero-Knowledge-Beweise \buchmann{15.4.3}}
Zero-Knowledge-Beweise sind neben den bereits vorgestellten Verfahren basierend auf symmetrischer Verschlüsselung und Signaturen ein drittes, interessantes Challenge-Response-Verfahren.

Zwei Eigenschaften haben alle drei Verfahren gemeinsam:
\begin{enumerate}
\item \textbf{Vollständigkeit} Ein ehrlicher Beweiser kann den Verifizierer fast immer von seiner Identität überzeugen.
\item \textbf{Korrektheit} Ein Betrüger hat nur eine sehr geringe Chance, sich als jemand anderes zu identifizieren.
\end{enumerate}

Neben diesen beiden gibt es noch eine dritte Eigenschaft, die Zero-Knowledge-Beweise zusätzlich besitzen:
\begin{enumerate}\setcounter{enumi}{2}
\item \textbf{Zero-Knowledge} Der Verifizierer erfährt mathematisch beweisbar nichts über das Geheimnis des Beweisers, obwohl er am Ende des Identifikationsprotokolls von dessen Identität überzeugt ist.
\end{enumerate}

\paragraph{Veranschaulichendes Beispiel}\label{zkbsp} Ein klassisches Beispiel zur Veranschaulichung ist Folgendes: Peggy möchte Victor davon überzeugen, dass sie über das geheime Wissen verfügt, eine Tür in einer Höhle zu öffnen ohne ihm dieses geheime Wissen (z.B. einen Schlüssel) zu zeigen. Das Protokoll ist in \figurename~\ref{zero_knowledge_bsp} dargestellt.

\begin{figure}[hbtp]
\centering
\myIncludeGraphics[scale=0.5]{Grafiken/zero_knowledge_bsp.png}
\caption{Beispiel für einen Zero-Knowledge-Beweis}
\label{zero_knowledge_bsp}
\end{figure}

Victor steht an Position 4 und beobachtet, wie Peggy in die Höhle hineingeht. Peggy entscheidet sich an Scheideweg 3 zufällig in welche Richtung sie geht, ohne dass Victor erkennen kann, wie sie sich verhält. Sie landet entweder links (1) oder rechts (2) von der verschlossenen Tür.

Victor geht nun zu 3 und wählt zufällig eine Richtung, aus der Peggy aus der Höhle zurückkommen soll. Er ruft nun bspw. in die Höhle, Peggy solle von links (1) aus der Höhle kommen. Jetzt gibt es zwei Möglichkeiten. Entweder stand Peggy bereits auf der linken Seite der Tür und sie kann ohne Schlüssel auf der richtigen Seite erscheinen oder sie stand rechts und musste den Schlüssel benutzen, um von 1 aus der Höhle zu kommen.

Victor kann also mit der Wahrscheinlichkeit $\frac{1}{2}$ sagen, dass Peggy das Geheimnis wirklich kennt. Um mehr Sicherheit zu erhalten, wiederholen Victor und Peggy das Protokoll $n$ mal. Nach $n$ erfolgreichen Versuchen ist Victor also mit der Wahrscheinlichkeit $1-2^{-n}$ davon überzeugt, dass Peggy das Geheimnis kennt.

\paragraph{Simulation}
Die Zero-Knowledge Eigenschaft kann durch Simulation bewiesen werden. Erzeugt ein Simulator, der einen zufälligen Nachrichtenaustausch gemäß dem Identifikationsprotokoll erzeugt, die gleiche Wahrscheinlichkeitsverteilung für die ausgetauschten Nachrichten, wie eine echte Protokollinstanz, ist der Nachrichtenaustausch offensichtlich nicht abhängig von dem Vorhandensein eines Geheimnisses. Damit wäre bewiesen, dass der Nachrichtenaustausch nicht vom Geheimnis des Beweisers abhängig ist und somit niemand aus einem Nachrichtenprotokoll Rückschlüsse auf das verwendete Geheimnis ziehen kann.

%>h3
\subsection{Das Fiat-Shamir-Verfahren \buchmann{15.4.3}}
Das Fiat-Shamir-Verfahren ist ein bekannter Zero-Knowledge-Beweis. Er basiert auf der Schwierigkeit, Quadratwurzeln im Restklassenring $\mathbb{Z}_{pq}$ zu berechnen. Dies ist genauso schwierig wie die Faktorisierung von $n=pq$.

\subsubsection{Funktionsweise des Protokolls} Das Identifikationsprotokoll des Fiat-Shamir-Verfahrens läuft wie folgt ab: 

Zunächst wählt der Beweiser analog dem RSA-Verfahren zwei Primzahlen $p$ und $q$ und berechnet den Modul $n=pq$. Nun wählt er eine Zahl $s$ zufällig und gleichverteilt mit: 
$$s \in (\Z/n\Z)^*$$ 
Das Quadrat $v=s^2\mod{n}$ wird zusammen mit $n$ als öffentlicher Schlüssel $(v,n)$ des Beweisers veröffentlicht. Sein geheimer privater Schlüssel ist die schwer zu berechnende Quadratwurzel $s$ von $v \mod{n}$.

Zur Identifikation möchte der Beweiser einem Verifizierer nachweisen, dass er eine Quadratwurzel für $v \mod{n}$ kennt, ohne ihm diese Quadratwurzel zu verraten. Eine einzelne Runde im Identifikationsprotokoll hat folgenden Ablauf:

\begin{enumerate}
\item \textbf{Commitment} Der Beweiser Peggy wählt zufällig und gleichverteilt ein $r \in \{1,2,...,n-1\}$, berechnet $x=r^2 \mod{n}$ und sendet $x$ an den Verifizierer Victor.
\item \textbf{Challenge} Victor wählt zufällig und gleichverteilt ein $e \in \{0,1\}$ und sendet es an Peggy.
\item \textbf{Response} Peggy berechnet eine Wurzel $y=rs^e \mod{n}$ und sendet es zur Identifikation an Victor.
\item Victor verifiziert, dass $y^2 \equiv xv^e \mod{n}$ und bestätigt somit Peggy's Identität.
\end{enumerate}

\subsubsection{Beispiel}
Peggy möchte Victor ihre Identität beweisen. Sie berechnet $$n=17*23=391$$ und wählt als geheimen Schlüssel $$s=123$$ somit gilt $$v=123^2 \mod{391}=271$$ Peggy's öffentlicher Schlüssel ist also $(271,391)$

Peggy teilt Victor mit, dass sie ihm jetzt gerne zeigen möchte, dass sie ein $s=271^{\frac{1}{2}} \mod{391}$ kennt und somit ihre Identität beweisen kann. Sie wählt zufällig $$r=173$$ und schickt Victor ein $$x=r^2 \mod{n}=213$$ Victor schickt ihr die Challenge $$e=1$$ zurück. Peggy berechnet $$y=rs^e \mod{n}=165$$ und sendet es Victor zu Verifikation. Victor verifiziert $$y^2=246 \equiv xv \mod{n}$$

\subsubsection{Zero-Knowledge-Beweis}
Zur Erläuterung des Protokolls soll nochmals auf das veranschaulichende Beispiel aus Kapitel \ref{zkbsp} eingegangen werden, indem der Beweiser aus einer vom Verifizierer vorgegebenen Richtung aus der Höhle kommen muss. Links oder rechts entsprechen im Fiat-Shamir-Verfahren dem zufällig gleichverteilt gewählten $e \in \{0,1\}$ 

\begin{description}
\item[1. Fall $e=0$] Der Beweiser muss $r$ kennen, da er ansonsten keine Quadratwurzel von $x$ finden könnte, damit die Verifikation $y^2=xv^0 \mod{n}$ gültig ist.
\item[2. Fall $e=1$] Der Beweiser muss $y$ kennen, da er ansonsten keine Quadratwurzel zu $xv$ finden könnte.
\end{description}

%-----------
Würde ein Betrüger versuchen, sich zu Identifizieren, ohne Kenntnis vom geheimen Schlüssel $s$ zu haben, müsste er $x$ aus einem festen $y$ berechnen: $$y^2 \equiv xv^e \mod{n}$$ $$y^2v^{-e} \equiv x \mod{n}$$
Ein Betrüger kann also nur für ein $e$ die Lösung kennen. 

\begin{description}
\item[1. Fall $e=0$] Der Betrüger kennt ein $y$ für das gilt $y^2 \equiv xv^0 \mod{n}$, also die Quadratwurzel von $x$ und kann somit die Frage nach $r$ beantworten.
\item[2. Fall $e=1$] Der Betrüger kennt ein $y$ für das gilt $y^2 \equiv xv^1 \mod{n}$, also die Quadratwurzel von $xv$.
\end{description}

Er kann jedoch nie beide Fragen beantworten. Der Betrüger kann nur mit der Wahrscheinlichkeit $\frac{1}{2}$ betrügen. Bezogen auf das Höhlen-Protokoll besitzt der Beweiser also nicht den Schlüssel um durch die Tür zu gelangen und kann nur aus der richtigen Seite kommen, wenn der Verifizierer zufällig die für den Betrüger günstige Seite wählt.

\subsubsection{Simulation}
In jedem Protokolldurchlauf des Fiat-Shamir-Verfahrens entsteht ein Nachrichtentripel $(x,e,y)$ mit folgenden Eigenschaften-
\begin{itemize}
\item $x$ ist ein gleichverteilt zufälliges Quadrat modulo $n$.
\item $e \in \{0,1\}$, das gemäß einer vom Verifizierers gewählten Verteilung ausgewählt wird.
\item $y$ ist eine gleichverteilt zufällige Quadratwurzel von $xv^e$ in modulo $n$.
\end{itemize}

Nun implementieren wir einen Simulator, der Tripel $(x,e,y)$ mit derselben Verteilung erzeugen kann. Der Simulator geht wie folgt vor:
\begin{description}
\item[Schritt 1]$\;$
\begin{itemize}
\item Auswahl eines gleichverteilt zufälligen $f \in \{0,1\}$.
\item Auswahl einer gleichverteilt zufälligen Zahl $y$ modulo $n$.
\end{itemize}
\item[Schritt 2] Berechnung eines $$x=y^2s^{-f} \mod{n}$$ also rückwärts aus gegebenem $y$ ein $x$. 
\item[Schritt 3] Auswahl eines $e \in \{0,1\}$ gemäß der Verteilung des Verifizierers.
\item[Schritt 4] Wenn $e=f$ Ausgabe des Tripel $(x,e,y)$, denn dann gilt $x=y^2s^{-f}$.
\end{description}
Somit wurde eine dem Originalprotokoll identische Wahrscheinlichkeitsverteilung simuliert. $x$ ist ein Zufallsquadrat modulo $n$, $e$ ist verteilt wie im Originalprotokoll und $y$ ist eine zufällige Quadratwurzel von $xs^e \mod{n}$.

\newpage
\section{Secret Sharing}\label{secretsharing}

\subsection{Prinzip \buchmann{16.1}}

\paragraph{Motivation:}
In den vergangenen Kapiteln wurde gezeigt, wie Public-Key-Verfahren und Private-Key-Verfahren eine sichere Übertragung von Nachrichten zwischen Parteien ermöglichen. Dazu wurde stets ein geheimer Schlüssel verwendet. Während die Kommunikation zwischen Sender und Empfänger einer Nachicht durch diese Verfahren gesichert wird, ist der geheime Schlüssel vor Verlust(unbeabsichtigte Zerstörung etwa durch Festplatten-Defekt) oder unbefugter Kenntnisnahme(Diebstahl) ungeschützt. Daher stellt sich die Frage, \textbf{wie der Schutz des geheimen Schlüssels erfolgen kann?}

\paragraph{Keine Lösung:}
Eine \textbf{Verschlüsslung} des geheimen Schlüssels analog der Verschlüsselung der Nachrichten bietet keine Lösung, sondern nur eine Verlagerung des Problems. Sie schützt weder vor Verlust noch vor unbefugter Kenntnisnahme. Denn schließlich entsteht so ein weiterer geheimer Schlüssel, den es zu schützen gilt. 

\subparagraph{Schutz vor unbefugter Kenntnisnahme:}
Durch Anwendung einer \textbf{Hashfunktion} kann ein geheimer Schlüssel gegen unbefugten Zugriff geschützt werden. Allerdings gelten Hashfunkionen als kollisionsresistente Einwegfunktionen und sind daher unumkehrbar. Der geheime Schlüssel kann nicht aus dem Hashwert errechnet werden. Damit bietet die Anwendung einer Hashfunktion zwar einen Schutz gegen unbefugte Kenntnisnahme, jedoch nicht gegen den Verlust des geheimen Schlüssels. Eine theoretische Lösung zur Gewährleistung des Schutzes vor unbefugter Kenntnisnahme besteht darin, den \textbf{Schlüssel zu löschen}. Allerdings steigt das Verlustrisiko auf $100\%$.

\subparagraph{Schutz gegen Verlust:}
Eine Möglichkeit den geheimen Schlüssel gegen Verlust abzusichern, besteht in der \textbf{Anfertigung mehrerer Kopien}. Diese können auf verschiedene Parteien (Personen, Speichermedien) verteilt werden. Der Verlust einer Kopie (z.B durch Defekt) hat keine Auswirkungen, da noch weitere Kopien des geheimen Schlüssels existieren. Mit der Anfertigung mehrerer Kopien steigt jedoch auch die Anzahl der zu schützenden Schlüssel und damit das Risiko vor unbefugter Kenntnisnahme.

\paragraph{Eine Lösung:}
Eine Lösung für dieses Problem bietet die \textbf{Zerlegung} eines geheimen Schlüssels in mehrere Teile und dessen \textbf{Verteilung} auf mehrere Personen. Dabei wird der geheime Schlüssel in $n$ Teilschlüssel (shares) zerlegt und an $n$ Personen (Geheimnisträger) verteilt. Anschließend kann eine beliebige Menge von $t$ Personen den geheimen Schlüssel aus deren Teilschlüsseln rekonstruieren, während weniger als $t$ Personen aus der Zusammenführung ihrer Teilschlüssel keine Informationen über den geheimen Schlüssel gewinnen können. Verfahren, bei denen ein geheimer Schlüssel auf $n$ Personen verteilt und von beliebigen $t$ Personen rekonstruiert werden kann, bezeichnet man als \textbf{$(n,t)$-Secret-Sharing-Verfahren}.

\paragraph{Anwendungen:}
Einsatzszenarien für \textbf{Secret-Sharing-Verfahren} sind die Absicherung des Private Key einer Person innerhalb eines Public-Key-Verfahrens oder eines geheimen Zugangscodes zu einem Tresor innerhalb einer Bank oder zu einem gesicherten Bereich innerhalb eines Labors oder einer Forschungseinrichtung. 

Damit bietet das Secret Sharing einen Schutz gegen den Verlust von geheimen Schlüsseln. Geht ein Teil des geheimen Schlüssels verloren (zum Beispiel durch Verlust oder Defekt einer Chipkarte), so kann der vollständige geheime Schlüssel aus einer bestimmten Anzahl von Teilschlüsseln reskonstruiert werden. 

Auch eine Verteilung von Verantwortlichkeiten wird durch das Secret Sharing ermöglicht. Der gesicherten Bereich des Labors kann nur von einer bestimmten Anzahl von Personen gleichzeitig und gemeinsam betreten werden. Auf diese Weise kann gegenseitige Kontrolle erfolgen.

Das Secret Sharing ermöglicht also den Schutz eines Geheimnisses vor Verlust und unberechtigten Zugriff. Im Gegensatz zu anderen Schutzmechanismen, wie Verschlüsselung oder Replizierung eines privaten Schlüssels, bietet das Secret-Sharing einen Schutz unter Berücksichtigung von Sicherheit und Verfügbarkeit der Geheimnisträger.

\subsection{Polynominterpolation \buchmann{16.2}}
Die Polynominterpolation bildet die mathematische Grundlage für das im Folgenden vorgestellte Secret-Sharing-Protokoll von Shamir. Es handelt sich dabei um ein Verfahren zur Bestimmung einer Funktion $f$ aus eine Anzahl $\ell$ vorliegender diskreter Wertepaare $(x_{i},y_{i})$ mit $y_{i} = f(x_{i})$. Dabei trägen $x_{i}$ und $y_{i}$ die Bezeichnung Stützstellen ($x_{i}$) und Stützwerte ($y_{i}$). Weiter ist von Bedeutung, dass die Stützstellen paarweise verschieden sind.

\begin{figure}[hbtp]
\centering
\myIncludeGraphics[scale=1.5]{Grafiken/Polynom_interpolation.png}
\caption{Beispiel eines Interpolationspolynoms siebten Grades mit $\ell = 8$ Wertepaaren}
\label{Interpolationspolynoms Beispiel}
\end{figure}

Dabei wird nun ein Polynom $b(X)$ eindeutig bestimmt für das die folgenden Eigenschaften gelten:

\begin{center}
\begin{enumerate}
\item Alle Paare $(x_{i},y_{i})$ werden von $b(X)$ durchlaufen. Es gilt: $\forall x_{i}, 1 \leq i \leq \ell : b(x_{i}) = y_{i}$ 
\item Der Grad $t$ von $b(X)$ ist kleiner als die Anzahl der Paare. Es gilt: deg $b(X) < \ell$
\end{enumerate}
\end{center}

\subsubsection{Lösung Gauß-Verfahren}
Liegen nun die Werte $(x_{i}, y_{i})$ von $\ell$ Paaren vor, kann das gesuchte Polynom in Form der Standardbasis $\{X^k|0 \le k < t\}$ geschrieben werden. Eine mögliche Darstellung von $b(X)$ ist daher die Schreibweise  $b(X) = a_{0} X^0 + a_{1} X^1 + ... + a_{t} X^t$. Werden nun die Paare $(x_{i},y_{i})$ in diese Gleichung eingesetzt, entsteht ein lineares Gleichungssystem aus $\ell$ Gleichungen. Das Gleichungssystem kann nun als eine Matrix (Stützstellen) mit zwei Vektoren (Koeffizienten, Stützwerte) geschrieben werden und mit Hilfe des Gauß-Verfahrens gelöst werden.\\
\\
\[
 \begin{pmatrix}
  1 & x_{0} & \cdots & x_{0}^{t-1} \\
  1 & \vdots & \ddots & \vdots \\
  1 & x_{\ell} & \cdots & x_{\ell}^{t-1} \\
 \end{pmatrix} 
 *
 \begin{pmatrix}
 a_{0} \\
 \vdots \\
 a_{t-1}
 \end{pmatrix} 
 = 
 \begin{pmatrix}
 y_{0} \\
 \vdots \\
 y_{\ell}
 \end{pmatrix}
\]
\\
Lässt sich dieses Gleichungssystem eindeutig lösen, können so die Koeffizienten des Interpolationspolynoms ermittelt werden.\\

\paragraph{Beispiel 1:} Es sind folgende Paare $(x_{i},y_{i})$ bekannt.
\subparagraph{Fall 1:  $\ell = t$} ($t$ = Anzahl der Unbekannten)
\begin{center}
\begin{itemize}
\item $(x_{1},y_{1}) = (1,15)$
\item $(x_{3},y_{3}) = (3,10)$
\item $(x_{5},y_{5}) = (5,6)$
\end{itemize}
\end{center}

Damit ist $\ell = 3$ und der Grad des gesuchten Polynoms $<3$. Aus den Werten $(x_{i},y_{i})$ ergeben sich die folgenden Gleichungen:

\begin{center}
\begin{itemize}
\item $b(1) = a_{0} + a_{1} * 1 + a_{2} * (1)^2 = 15$
\item $b(3) = a_{0} + a_{1} * 3 + a_{2} * (3)^2 = 10$
\item $b(5) = a_{0} + a_{1} * 5 + a_{2} * (5)^2 = 6$
\end{itemize}
\end{center}

Daraus folgt:\\
\[
\left(
 \begin{matrix}
  1 & 1 & 1\\
  1 & 3 & 9\\
  1 & 5 & 25\\
 \end{matrix}
 \left|
  \begin{matrix}
  15 \\
  10 \\
  6 \\
  \end{matrix}
 \right)
\right.
\]
\begin{center}
Multipliziere Spalte 1 mit (-1) und addiere Spalte 2 und anschließend Spalte 3
\end{center}
\[
\left(
 \begin{matrix}
  1 & 1 & 1\\
  0 & 2 & 8\\
  0 & 4 & 24\\
 \end{matrix}
 \left|
  \begin{matrix}
  15 \\
  -5 \\
  -9 \\
  \end{matrix}
 \right)
\right.
\]
\begin{center}
Multipliziere Spalte 2 mit (-2) und addiere Spalte 3
\end{center}
\[
\left(
 \begin{matrix}
  1 & 1 & 1\\
  0 & 2 & 8\\
  0 & 0 & 8\\
 \end{matrix}
 \left|
  \begin{matrix}
  15 \\
  -5 \\
  1 \\
  \end{matrix}
 \right)
\right.
\]

Damit besitzt das Gleichungssystem eine eindeutige Lösung für $\ell$ = $t$. Die Koeffizienten $a_{0}$, $a_{1}$ und $a_{2}$ des gesuchten Polynoms können nun bestimmt werden:
\[
 8 * a_{2} = 1 = \frac{1}{8}
\]
\[
 2 * a_{1} + 8 * \frac{1}{8} = -3
\]
\[
 1 * a_{0} + 2 * (-3) + 8 * \frac{1}{8} = \frac{143}{8}
\]
Damit ist $b(X)$ das gesuchte Polynom mit:
\[
b(X) = \frac{143}{8} - \frac{24}{8}X + \frac{1}{8}X^2
\]
Durch Einsetzen der Werte $x_{i}$ kann gezeigt werden, dass das Polynom, die geforderten Eigenschaften besitzt, da dessen Grad $deg = 2 < t$ ist.
\[
b(1) = \frac{143}{8} - \frac{24}{8} * 1 + \frac{1}{8}* (1)^2 = \frac{120}{8} = 15
\]

\[
b(3) = \frac{143}{8} - \frac{24}{8} * 3 + \frac{1}{8}*(3)^2 = \frac{80}{8} = 10
\]

\[
b(5) = \frac{143}{8} - \frac{24}{8} * 5 + \frac{1}{8}* (5)^2 = \frac{48}{8} = 6
\]
Für die Bestimmung des Interpolationspolynoms $b(X)$ wurden bisher die reellen Zahlen zugrunde gelegt. Im Rahmen des Secret-Sharing werden die Koeffizienten ($a_{0}$, $a_{1}$, $...$) von $b(X)$ jedoch aus der primen Restklassengruppe $\Z/p\Z$ gewählt. Um nun zu prüfen, ob die Ergebnisse aus Beispiel 1 auch in $\Z/p\Z$ Gültigkeit besitzen, werden die Koeffizienten modulo einer Primzahl p invertiert. Hier sei $p=17$ und das Inverse $y_{2}= -2$.
\definecolor{dunkelgrau}{rgb}{0.8,0.8,0.8}
\begin{center}
\begin{tabular}{|c|ccc|}
\hline
$k$ & $0$ & $1$ & $2$ \\
\hline
$r_k$ & $17$ & $8$  & $1$\\
$q_k$ & $1$  &  $2$ & $8$\\
$x_k$ & $1$  &  $0$ & \cellcolor{dunkelgrau}$1$ \\
$y_k$ & $0$  &  $1$ & \cellcolor{dunkelgrau}$2$ \\
\hline 
\end{tabular}
\end{center}
$$1 * 17 + (-2) * 8 = 1$$
$$x_2=1,y_2=-2$$

Werden nun die Koeffizienten von $b(X)$ mit $-2$ multipliziert und anschließend mod $17$ gerechnet folgt:

\[
a_{0}: 143 * (-2) = -286  \equiv 3\mod17 
\]

\[
a_{1}: 24 * (-2) = -48  \equiv 3\mod17 
\]

\[
a_{2}: 1 * (-2) = -2  \equiv 15\mod17 
\]

Für $b(X)$ gilt damit:

\[
b(X) = 3 -3X + 15X^2
\]

Nun können auch hier $x_{1}=1$, $x_{3}=3$ und $x_{5}=5$ eingesetzt werden.

\[
b(1) = 3 -3 * 1 + 15 * (1)^2 = 15 \mod17 = 15 = y_{1}
\]

\[
b(3) = 3 -3 * 3 + 15 * (3)^2 = 129 \mod17 = 10 = y_{3}
\]

\[
b(5) = 3 -3 * 5 + 15 * (5)^2 = 363 \mod17 = 6 = y_{5}
\]

Es lässt sich also zeigen, dass die Berechnungen aus Beispiel 1 auch in $\Z/p\Z$ Gültigkeit besitzen.

\subparagraph{Fall 2: $\ell < t$}
\begin{center}
\begin{itemize}
\item $(x_{1},y_{1}) = (1,15)$
\item $(x_{3},y_{3}) = (3,10)$
\end{itemize}
\end{center}
Ist $\ell < t$ entsteht ein heterogenes Gleichungssystem, dass nicht eindeutig gelöst werden kann. Es existieren mehr Unbekannte (Koeffizienten $a_{i}$) als unabhängige Gleichungen, die deren Bestimmung ermöglichen. Die Koeffizientenmatrix aus Fall 1 gliedert sich dann in zwei Bereiche. Einen linken Teil, der die $\ell$ x $\ell$-obere Dreiecksmatrix bildet, die durch Anwendung des Gauß-Verfahrens entsteht. Sowie einen rechten Teil, der eine $\ell$ x $(t-\ell)$ Matrix bildet, welche die nicht bestimmbaren Koeffizienten $a_{k} , \ell < k \leq t$ enthält. Daraus ergibt sich folgende Darstellung.

\[
  \left( 
	\begin{matrix} 
    1 		& 1\\
    0 		& 1\\
    \end{matrix}
  \right.
\: \: \: \: \: \:
  \left.
	\begin{matrix}
    \star \\
    \star \\
	\end{matrix}
  \right)
  *
 \left.
 \begin{pmatrix}
 	a_{0} \\
 	a_{1} \\
 	a_{2} \\
 \end{pmatrix}
 \right.
 	= 
 \begin{pmatrix}
 y_{0} \\
 y_{1} \\
 \end{pmatrix}
\]

Zur Ermittlung der Lösungen des Gleichungssystems in Beispiel 1 können nun die möglichen Werte für $a_{2}$ eingesetzt werden. Für jeden Wert von $a_{2}$ werden die Koeffzienten $a_{1}$ und $a_{0}$ festgelegt. Dabei werden Koeffizienten $a_{i}$ aus der primen Restklassengruppe $\Z/p\Z$ gewählt. Diese besitzt die Ordnung $p-1$. Zusammen mit der $0$, ergeben sich damit $p$ mögliche Werte für $a_{2}$. Allgemein gibt es daher für $\ell < t$ die Anzahl von $p^{t-\ell}$ Lösungen für das Gleichungssystem.\\
\\
Das Interpolationsploynom $b(X)$ kann also eindeutig bestimmt werden, wenn die Anzahl der Paare $\ell$ mit der Anzahl $t$ der Koeffzienten $a_{i}$ übereinstimmt. Es also gilt $p^{t-\ell} = p^0 = 1$. Daraus folgt auch, dass das gesuchte Polynoms $b(X)$ höchstens den Grad $t-1$ besitzen kann. Angenommen, Stützstellen und Stützwerte stimmen für alle Punkte innerhalb eine Gruppe überein ($x_{i}= y_{i}$), so ist das Interpolationspolynom eine Gerade vom Grad eins.

\subsubsection{Lösung Lagrange-Polynome}
Da die Lösung des linearen Gleichungssystems bei großen $t$ und $\ell$ mit Hilfe des Gauß-Verfahren sehr aufwändig wird, kann das Gleichungssystem mit Hilfe des Lagrange-Polynoms effizienter gelöst werden. Dieses hat im Allgemeinen die folgende Form: 
\[
  b(X) := \sum_{i=1}^{t} y_i \prod_{j \ne i}^t \frac{x_j - X}{x_j - x_i}
\]
\[
L_{i}(X) = \prod_{j \ne i}^t \frac{x_j - X}{x_j - x_i}
\]
\[
  b(X) := \sum_{i=1}^{t} y_i * L_{i}(X)
\]

\paragraph{Beispiel 2:}
Wie in Beispiel 1 werden auch hier die folgenden drei Paare als gegeben betrachtet.
\begin{center}
\begin{itemize}
\item $(x_{1},y_{1}) = (1,15)$
\item $(x_{3},y_{3}) = (3,10)$
\item $(x_{5},y_{5}) = (5,6)$
\end{itemize}
\end{center}

Im ersten Schritt werden nun die Produkte $L_{i}(X)$ berechnet:

\[
L_{1}(X) = \frac{(x_3 - X)(x_5 - X)}{(x_3 - x_1)(x_5 - x_1)} = \frac{(3 - X)(5 - X)}{(3 - 1)(5 - 1)} = \frac{15 -8X + X^2}{8}
\]

\[
L_{3}(X) = \frac{(x_1 - X)(x_5 - X)}{(x_1 - x_3)(x_5 - x_3)} = \frac{(1 - X)(5 - X)}{(1 - 3)(5 - 3)} = \frac{5 -6X + X^2}{-4}
\]

\[
L_{5}(X) = \frac{(x_1 - X)(x_3 - X)}{(x_1 - x_5)(x_3 - x_5)} = \frac{(1 - X)(3 - X)}{(1 - 5)(3 - 5)} = \frac{3 -4X + X^2}{8}
\]

Anschließend kann $b(X)$ berechnet werden:

\[
  b(X) := \sum_{i=1}^{t} y_i * L_{i}(X) = 15 * L_{1}(X) + 10 * L_{3}(X) + 6 * L_{5}(X)
\]

\[
  b(X) := 15 * \frac{15 -8X + x^2}{8} + 10 * \frac{5 -6X + x^2}{-4} + 6 * \frac{3 -4X + x^2}{8}
\]

\[
  b(X) := \frac{225}{8} - \frac{120}{8}X + \frac{15}{8}X^2 - \frac{100}{8} + \frac{120}{8}X - \frac{20}{8}X^2 + \frac{18}{8} -\frac{24}{8}X + \frac{6}{8}X^2
\]

\[
  b(X) := \frac{143}{8} - \frac{24}{8}X + \frac{1}{8}X^2
\]

Es wird ersichtlich, dass es sich bei $b(X)$ um dasselbe Polynom aus Beispiel 1 handelt. Die Prüfung der $y_{i}$ kann daher, an dieser Stelle, entfallen.

\subsection{Shamir-Secret-Sharing-Protokoll \buchmann{16.2}}
An dieser Stelle wird nun des Secret-Sharing das Secret-Sharing-Protokoll vom Shamir beschrieben. Hier seien $n,t \in \N$ mit $t \leq n$ und eine Primzahl $p$. Das Protokoll selbst umfasst die drei Schritte Initialisierung, Verteilung der Geheimnisanteile und Reskonstruktion des Geheimnisses. Diese werden im folgenden beschrieben.

\subsubsection{Initialisierung \buchmann{16.2.1}}
Zur Initialisierung des Protokolls wählt eine vertrauenwürdige Stelle (Dealer) eine Primzahl $p$ mit $p \geq n + 1$ und paarweise verschiedene Elemente $x_{i}$ $\in$ $\Z/p\Z$ mit $1 \leq i \leq n$. Da die Berechnungen im Körper $\Z/p\Z$ erfolgen, sind die Elemente $x_{i}$ Restklassen und werden durch ihre kleinste nicht negativen Vertreter repäsentiert. Die $x_{i}$ werden veröffentlicht.

\subsubsection{Verteilung der Geheimnisanteile \buchmann{16.2.2}}
Nach der Initialisierung erfolgt die Zerlegung des Geheimnisses (geheimeinen Schlüssels) durch Berechnung von $n$ Geheimnissanteilen $y_{i}$ und deren Verteilung an $n$ Personen. Auch hier gilt, die einzelnen Schritten werden von einer vertrauenswürdigen Stelle vorgenommen.

\begin{enumerate}
\item \textbf{Schritt 1:} Im ersten Schritt erfolgt die Auswahl des Geheimnis $s$ $\in$ $\Z/p\Z$.

\item \textbf{Schritt 2:} Im zweiten Schritt werden zufällige Koeffizienten $a_{i}$ $\in$ $\Z/p\Z$ mit $1 \leq j \leq t - 1$ gewählt.

\item \textbf{Schritt 3:} Im dritten Schritt wird ein Polynom $a(X)$ aus dem Geheimnis $s$ und den Koeffizienten $a_{i}$  konstruiert. Dabei gilt, $a(X)$ ist vom Grad $\leq t - 1$. Damit gilt: $a(0) = s$. Das Geheimnis ist also der konstante Term des Polynoms. Das Polynom wird geheim gehalten.

\[
a(X) = s + \sum_{j=1}^{t-1} a_{j} X^j
\]

\item \textbf{Schritt 4:} Mit Hilfe des Polynoms $a(X)$ und den Stützstellen $x_{i}$ werden im vierten Schritt die Geheimnisanteile $y_{i}$ der $n$ Personen berechnet. Dabei erhält jede $i-te$ Person den ensprechenden Geheimnisanteil $y_{i}$.

\end{enumerate}

\paragraph{Beispiel:} Bekannt sind: $n = 5$, $t = 3$, $p = 17$ und $x_{i} = i, 1 \leq i \leq n$. Im ersten Schritt erfolgt die Auswahl von $s$ $\in$ $\Z/p\Z$ durch den Dealer. Hier $s = 3$. Die geheimen Koeffizienten sind $a_{i} = 13 + i$ mit $1 \leq i \leq 2$. Aus dem Geheimnis $s$ und den Koeffizienten $a_{i}$ ergibt sich folgendes Polynom zweiten Grades (da $t-1 = 3-1 = 2$ gilt):
\[
a(X) = 15X^2 + 14X + 3
\]
Aus dem Polynom $a(X)$ und den Stützstellen $x_{i}$ können nun die Geheimnissanteile $y_{i}$ bestimmt und an die $n$ Geheimnisträger verteilt werden. 
\begin{center}
\begin{itemize}
\item $y_{1}$ = $a(x_{1}) = (15 * (1)^2 + 14 * (1) + 3)$ mod $17 = 15$ 
\item $y_{2}$ = $a(x_{2}) = (15 * (2)^2 + 14 * (2) + 3)$ mod $17 = 6$ 
\item $y_{3}$ = $a(x_{3}) = (15 * (3)^2 + 14 * (3) + 3)$ mod $17 = 10$
\item $y_{4}$ = $a(x_{4}) = (15 * (4)^2 + 14 * (4) + 3)$ mod $17 = 10$
\item $y_{5}$ = $a(x_{5}) = (15 * (5)^2 + 14 * (5) + 3)$ mod $17 = 6$
\end{itemize}
\end{center}
Es ergeben sich also folgende Paare $(x_{i},y_{i})$ für Stützstellen und Stützwerte:
\begin{center}
\begin{itemize}
\item $(x_{1},y_{1}) = (1, 15)$
\item $(x_{1},y_{1}) = (2, 6)$
\item $(x_{1},y_{1}) = (3, 10)$
\item $(x_{1},y_{1}) = (4, 10)$
\item $(x_{1},y_{1}) = (5, 6)$
\end{itemize}
\end{center}

\subsubsection{Rekonstruktion des Geheimnisses \buchmann{16.2.3}}
Zur Rekonstruktion des Geheimisses, müssen nun beliebige $t$ Geheimnisträger zusammentreffen. Ist dies der Fall, kann das Geheimnis aus deren Geheimnisanteilen $y_{i}$ und dem Polynmon $a(X)$ aus dem Lagrange-Interpolationsverfahren rekonstruiert werden. Dabei gilt:
\[
  a(X) := \sum_{i=1}^{t} y_i \prod_{j \ne i}^t \frac{x_j - X}{x_j - x_i}
\]
Da das Geheimnis dem konstanten Term von $a(X)$ entspricht und die ausreichende Anzahl von $y_{i}$ mit $1 \leq i \leq t$ vorhanden ist, kann die Rekonstruktion durch $a(0)$ erfolgen:
\[
  a(0) := \sum_{i=1}^{t} y_i \prod_{j \ne i}^t \frac{x_j}{x_j - x_i}
\]
\paragraph{Beispiel:} Die ersten drei Geheimnisträger aus dem oberen Beispiel rekonstruieren das Geheimnis. Dazu werden die Werte $x_{i}$ aus dem Paar $(x_{i},y_{i})$ genutzt, um die Produkte $L_i(0) = \prod_{j \ne i}^t \frac{x_j}{x_j - x_i}$ zu berechnen. Anschließend werden $L_i(0)$ und $y_{i}$ für alle $i$ aufsummiert und die Summe mod $p$ berechnet.
\begin{center}
\[
L_1(0) = \frac{x_{2}}{x_{2} - x_{1}} * \frac{x_{3}}{x_{3} - x_{1}} = \frac{2}{2 - 1} * \frac{3}{3 - 1} = \frac{2 * 3}{1 * 2} = \frac{6}{2} = 3
\]

\[
L_2(0) = \frac{x_{1}}{x_{1} - x_{2}} * \frac{x_{3}}{x_{3} - x_{2}} = \frac{1}{1 - 2} * \frac{3}{3 - 2} = \frac{1 * 3}{(-1) * 1} = \frac{3}{ (-1)} = -3
\]

\[
L_3(0) = \frac{x_{1}}{x_{1} - x_{3}} * \frac{x_{2}}{x_{2} - x_{3}} = \frac{1}{1 - 3} * \frac{2}{2 - 3} = \frac{1 * 2}{(-2) * (-1)} = \frac{2}{2} = 1
\]
\end{center}
Die berechneten Produkte $L_i(0)$ und die Geheimnisanteile $y_{i}$ werden nun mittels des Lagrange-Interpolations multipliziert und aufsummiert.
\begin{center}
\[ 
a(0) = (3 * 15 + (-3) * 6 + 1 * 10)\mod 17 
\]

\[ 
a(0) = 37 \equiv 3\mod 17
\]
\end{center}
Damit ist das Geheimnis $s = 3$ rekonstruiert.

\subsubsection{Sicherheit \buchmann{16.2.4}}
Für die Sicherheit des Secret-Sharing-Verfahrens ist entscheidend, dass bei $\ell < t$ Punkten ($x_{i},y_{i}$) jeder konstante Term $a_{0}$ des Polynoms gleichwahrscheinlich ist. Dies wird aus Fall 2 in Beispiel 1 zur Ermittlung des Interpolationspolynoms $b(X)$ ersichtlich, da hier $a_{0}$ beliebig aus $\Z/p\Z$ gewählt werden kann. Die folgende Abbildung veranschaulicht dies nochmals an einen ähnlichen Beispiel.
\begin{figure}[hbtp]
\centering
\myIncludeGraphics[scale=0.5]{Grafiken/security_two_points.png}
\caption{Beispiel: Polynome mit zwei gegebenen Punkten}
\label{Beispiel: Polynome mit zwei gegebenen Punkten}
\end{figure}

Alle vier beispielhaft dargestellten Polynome (ermittelt aus den Paaren ($x_{1},y_{1}$) und ($x_{3},y_{3}$)) besitzen verschiedene konstante Werte für $a_{0}$ innerhalb des Geheimnisraums. Dieser wird durch die rote Y-Achse des Koordinationssystems dargestellt. Durch das Vorliegen der zwei Punkte wird der Geheimnisraum nicht eingechränkt. Aus den zwei Punkten können keine relvanten Informationen über das Geheimnis gewonnen werden. Liegt nun noch der dritte Punkt ($x_{2},y_{2}$) vor, kann das Polynom eindeutig bestimmt werden.
\begin{figure}[H]
\centering
\myIncludeGraphics[scale=0.5]{Grafiken/security_three_points.png}
\caption{Beispiel: Polynome mit drei gegebenen Punkten}
\label{Beispiel: Polynome mit drei gegebenen Punkten}
\end{figure}
Es gilt: Auch wenn $m$ Geheimnisträger mit $m < t$ wissen, dass das Geheimnis $s$ der konstante Term eines Polynoms $b(X)$ mit dem Grad $t - 1$ ist, erhalten diese keine Kenntnis vom Geheimnis $s$, da jedes $s' \in \Z/p\Z$ gleichwahrscheinlich ist.
\ifdefined\isGesamtDokument
\else
\newpage
\section{Übungen}
\subsection{Zu Kapitel \ref{identifikation}}
\input{uebung1.tex}
\input{uebung2.tex}
\input{uebung3.tex}
\input{uebung4.tex}
\subsection{Zu Kapitel \ref{secretsharing}}
\input{uebung5.tex}
\input{uebung6.tex}
\input{uebung7.tex}
\input{uebung8.tex}
\input{footer.tex}
\fi